package com.hqq.search.red_black_tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * RedBlackTreeSearch
 * 红黑树的实现
 * Created by heqianqian on 2017/8/6.
 */
public class RedBlackTreeSearch<K extends Comparable<K>, V> {

    private static final boolean RED = true;//表示红色
    private static final boolean BLACK = false;//表示黑色

    public Node root;

    /**
     * 判断节点是否是红色
     *
     * @param x 节点
     * @return 节点颜色
     */
    public boolean isRed(Node x) {
        if (x == null) {
            return false;
        }
        return x.color == RED;
    }

    /**
     * 左旋转
     */
    public Node rotateLeft(Node h) {
        Node x = h.right;
        h.right = x.left;
        x.left = h;
        x.color = h.color;
        h.color = RED;
        x.N = h.N;
        h.N = 1 + size(h.left) + size(h.right);
        return x;
    }

    /**
     * 右旋转
     */
    public Node rotateRight(Node h) {
        Node x = h.left;
        h.left = x.right;
        x.right = h;
        x.color = h.color;
        h.color = RED;
        x.N = h.N;
        h.N = 1 + size(h.left) + size(h.right);
        return x;
    }

    /**
     * 计算x节点的子节点个数
     */
    public int size(Node x) {
        if (x == null) {
            return 0;
        }
        return x.N;
    }

    public void put(K key, V value) {
        //查找key 找到就更新值 否则新建一个节点
        root = put(root, key, value);
        root.color = BLACK;//插入节点默认都是黑色节点
    }

    private Node put(Node h, K key, V value) {
        if (h == null) {
            return new Node(key, value, 1, RED);
        }
        int cmp = key.compareTo(h.key);
        if (cmp < 0) {//如果插入的节点比当前节点小
            h.left = put(h.left, key, value);
        } else if (cmp > 0) {
            h.right = put(h.right, key, value);
        } else {
            h.value = value;
        }
        if (isRed(h.right) && isRed(h.left)) {
            //如果左右罪数都是红色的话 那么直接进行颜色交换
            flipColor(h);
        } else if (isRed(h.left) && isRed(h.left.left)) {
            //左子树为红 且左子树的右子树也是红 那么进行左旋转
            h = rotateRight(h);
        } else if (isRed(h.right) && !isRed(h.left)) {
            //左子树不为红 但右子树为红 进行左旋转
            h = rotateLeft(h);
        }
        h.N = size(h.left) + size(h.right) + 1;
        return h;
    }

    /**
     * 交换颜色
     * 将两个字节点的颜色设置为黑色 当前节点的颜色设置为红色
     *
     * @param h
     */
    private void flipColor(Node h) {
        h.color = RED;
        h.left.color = BLACK;
        h.right.color = BLACK;
    }

    public void print(Node node) {
        if (node == null) {
            return;
        }
        print(node.left);
        System.out.println(node.value);
        print(node.right);
    }

    /**
     * 范围查找操作
     */
    public Iterable<K> keys() {
        return keys(min(), max());
    }

    public K min() {
        return min(root).key;
    }

    private Node min(Node node) {
        if (node.left == null) {
            return node;
        }
        return min(node.left);
    }

    public K max() {
        return max(root).key;
    }

    public Node max(Node node) {
        if (node.right == null) {
            return node;
        }
        return max(node.right);
    }

    private Node moveRedLeft(Node h) {
        //假设节点h是红色 节点的左子节点和左子节点的左子节点都是黑色
        //将节点的左子节点和左子节点的左子节点之一变成红色
        flipColor(h);
        if (isRed(h.right.left)) {
            //如果右节点的左及节点是红色
            h.right = rotateRight(h.right);
            h = rotateLeft(h);//自己再进行左转
        }
        return h;
    }

    public Iterable<K> keys(K low, K high) {
        Queue<K> queue = new LinkedList<>();
        keys(root, queue, low, high);
        return queue;
    }

    private void keys(Node node, Queue<K> queue, K low, K high) {
        if (node == null) {
            return;
        }
        int cmpLow = low.compareTo(node.key);
        int cmpHigh = high.compareTo(node.key);
        if (cmpLow < 0) {
            keys(node.left, queue, low, high);
        }
        if (cmpLow <= 0 && cmpHigh >= 0) {
            queue.add(node.key);
        }
        if (cmpHigh > 0) {
            keys(node.right, queue, low, high);
        }
    }

    private class Node {
        K key;//键
        V value;//值
        Node left, right;//左右子树
        int N;//子树中节点的总数
        boolean color;//父节点指向它的连接的颜色

        public Node(K key, V value, int n, boolean color) {
            this.key = key;
            this.value = value;
            N = n;
            this.color = color;
        }
    }
}
